package com.cjm.algorithm.tanxin;

import java.util.HashMap;

public class Ti134 {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int curSum = 0;
        int totalSum = 0;
        int start = 0;
        for (int i = 0; i < gas.length; i++) {
            curSum += gas[i] - cost[i];// 当前还剩下多少油
            totalSum += gas[i] - cost[i];// 当前总的油
            if (curSum < 0) {// 如果出现负数了， 那么证明跑不完
                start = i + 1;// 重新开始
                curSum = 0;// 也是0
            }
        }
        if (totalSum < 0) {// 如果总的油量小于花费油量， 则不够
            return -1;
        }
        return start;
    }

    void slidingWindow(String s) {
        HashMap<Character, Integer> window = new HashMap<Character, Integer>();
        int left = 0, right = 1;
        while (left < right && right < s.length()) {
            Character c = s.charAt(right);
            // 将这个元素放入到窗口中去
            window.put(c, window.getOrDefault(c, 0) + 1);
            // 将窗口加大
            right++;
            // 进行窗口内一系列数据的更新
            // bug出现的地方

            // 接下来，判断这个窗口是否需要缩小
            while (left < right && needShrink(window)) {
                // 左侧的元素
                char leftChar = s.charAt(left);
                // 将这个元素移除
                window.put(leftChar, window.get(leftChar) - 1);
                // 将这个窗口缩小
                left++;
            }
        }
    }

    private boolean needShrink(HashMap<Character, Integer> window) {
        // Implement the logic to determine if the window needs to shrink
        return false; // Placeholder return value
    }

    public String minWindow(String s, String t) {
        HashMap<Character, Integer> need = new HashMap<Character, Integer>(), window = new HashMap<Character, Integer>();
        for (char item : t.toCharArray()) {
            need.put(item, need.getOrDefault(item, 0) + 1);
        }

        int left = 0, right = 0;
        int valid = 0;
        int start = 0, len = Integer.MAX_VALUE;
        while (right < s.length()) {
            Character c = s.charAt(right);
            right++;

            if (need.containsKey(c)) {
                window.put(c, window.getOrDefault(c, 0) + 1);
                if (need.get(c).equals(window.get(c))) {
                    valid++;
                }
            }

            while (valid == need.size()) {
                if (right - left < len) {
                    start = left;
                    len = right - left;
                    Character d = s.charAt(left);
                    left++;
                    if (need.containsKey(d)) {
                        if (window.get(d).equals(need.get(d))) {
                            valid--;
                        } else {
                            window.put(d, window.get(d) - 1);
                        }
                    }
                }
            }
        }
        return left == Integer.MIN_VALUE ? "" : s.substring(start, len);
    }
}
